//给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短
//序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。 
// 示例： 
// 输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
//输出： [3,9]
// 
// 提示： 
// 
// 0 <= len(array) <= 1000000 
// 
//
// Related Topics 栈 贪心 数组 双指针 排序 单调栈 👍 135 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;

/**
 * @author ldltd
 * @date 2025-09-08 19:32:44
 * @description 面试题 16.16.部分排序
 */
public class SubSortLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SubSortLcci fun=new SubSortLcci();
	 	 Solution solution = fun.new Solution();
			solution.subSort(new int[]{1,3,9,7,5});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int[] subSort1(int[] array) {
		if (array.length == 0) return new int[]{-1, -1};

		ArrayDeque<Integer> st = new ArrayDeque<>();
		st.push(0);
		int max = array[0];
		int right = -1;
		// 构建初始有序部分
		int i = 1;
		while (i < array.length && array[i] >= array[st.peek()]) {
			st.push(i);
			max = array[i];
			i++;
		}
		// 整个数组有序
		if (i == array.length) {
			return new int[]{-1, -1};
		}
		// 处理剩余元素
		for (; i < array.length; i++) {
			// 弹出所有比当前元素大的元素
			while (!st.isEmpty() && array[i] < array[st.peek()]) {
				st.pop();
			}
			// 如果当前元素小于最大值，需要排序
			if (array[i] < max) {
				right = i;
			} else {
				max = array[i];
			}
		}
		// 确定结果
		if (right == -1) {
			return new int[]{-1, -1};
		}
		if (st.isEmpty()) {
			return new int[]{0, right};
		}
		return new int[]{st.peek() + 1, right};
	}

	//双指针
	public int[] subSort(int[] array) {
		if(array == null || array.length == 0) return new int[]{-1, -1};
		int last = -1, first = -1;
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		int len = array.length;
		for(int i = 0; i < len; i++){
			if(array[i] < max){
				// 更新右边界和最大值
				last = i;
			}else{
				max = Math.max(max, array[i]);
			}

			if(array[len - 1 - i] > min){
				// 更新左边界和最小值
				first = len - 1 - i;
			}else{
				min = Math.min(min, array[len - 1 - i]);
			}
		}
		return new int[] {first, last};
	}

	public int[] subSor(int[] array) {
		if (array.length == 0) return new int[]{-1, -1};

		int n = array.length;
		int left = -1, right = -1;
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;

		// 从左到右遍历，找到最后一个小于当前最大值的索引（右边界）
		for (int i = 0; i < n; i++) {
			if (array[i] >= max) {
				max = array[i];
			} else {
				right = i;
			}
		}

		// 从右到左遍历，找到最后一个大于当前最小值的索引（左边界）
		for (int i = n - 1; i >= 0; i--) {
			if (array[i] <= min) {
				min = array[i];
			} else {
				left = i;
			}
		}

		return new int[]{left, right};
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
